
# Tree

class TreeNode:
    # Attributes: value, left, right
    # Constructor
    def __init__(self, value, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

    # Methods
    def __str__(self):
        if self.left == None and self.right == None:
            return f"V:{self.value} L:None R:None"
        elif self.left == None:
            return f"V:{self.value} L:None R:{self.right.value}"
        elif self.right == None:
            return f"V:{self.value} L:{self.left.value} R:None"
        else:
            return f"V:{self.value} L:{self.left.value} R:{self.right.value}"

class BinaryTree:
    # Constructor
    # root = None -> Empty Binary Tree
    def __init__(self, root = None):
        self.root = root
    
    # Methods
    # node - starting point
    # dfs - Deep First Search 深度优先搜索
    def dfs(self, node):
        if node == None:
            return
        
        print(f"{node.value}, ")
        self.dfs(node.left)
        self.dfs(node.right)
    
    def preorder(self):
        self.dfs(self.root)

    def dfs_inorder(self, node):
        if node == None:
            return
        
        self.dfs_inorder(node.left)
        print(f"{node.value}")
        self.dfs_inorder(node.right)

    def inorder(self):
        self.dfs_inorder(self.root)

    def dfs_postorder(self, node):
        if node == None:
            return
        
        self.dfs_postorder(node.left)
        self.dfs_postorder(node.right)
        print(f"{node.value}")
    
    def postorder(self):
        self.dfs_postorder(self.root)


eleven   = TreeNode(value = 11)
twelve   = TreeNode(value = 12)
thirteen = TreeNode(value = 13)
fourteen = TreeNode(value = 14)
fifteen  = TreeNode(value = 15)
sixteen  = TreeNode(value = 16)
seventeen = TreeNode(value = 17)
twenty = TreeNode(value = 20)

eleven.left = twelve
eleven.right = thirteen

twelve.left = fourteen
twelve.right = fifteen

thirteen.left = sixteen
thirteen.right = seventeen

sixteen.left = twenty

tree = BinaryTree(root = eleven)

# 如何能够确保树的结构是正确的？
# 必须有一种可以遍历树的方法
# 通过遍历树的结果，来检查树的结构

tree.postorder()

# Homework
# 1. 自己实现 TreeNode 和 BinaryTree
# 2. 自己构建一颗层数不少于 3 层的二叉树
# 3. 心算二叉树的 preorder 结果
# 4. 通过程序验证心算结果
